\documentclass[10pt]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usetheme{metropolis}
\usepackage{booktabs}
\usepackage[scale=2]{ccicons}
\usepackage{pgfplots}
\usepgfplotslibrary{dateplot}
\usepackage{xspace}
\usepackage{pbox}

% a few macros
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\ig}{\includegraphics}
\definecolor{hilight}{RGB}{235,129,27}
\definecolor{vhilight}{RGB}{235,129,27}

% title info
\title{Dynamic Programming}
\author{Bjarki Ágúst Guðmundsson\\ Tómas Ken Magnússon}
\institute{\href{http://ru.is/td}{School of Computer Science} \\[2pt] \href{http://ru.is}{Reykjavík University}}
\titlegraphic{\hfill\includegraphics[height=0.6cm]{kattis}}
\date{\textbf{Árangursrík forritun og lausn verkefna}}

% Tikz
\usepackage{tikz}
\usetikzlibrary{arrows,shapes}

% Minted
\usepackage{minted}
\usemintedstyle{manni}
\newminted{cpp}{fontsize=\footnotesize}

% Graph styles
\tikzstyle{vertex}=[circle,fill=black!50,minimum size=15pt,inner sep=0pt, font=\small]
\tikzstyle{selected vertex} = [vertex, fill=red!24]
\tikzstyle{edge} = [draw,thick,-]
\tikzstyle{dedge} = [draw,thick,->]
\tikzstyle{weight} = [font=\scriptsize,pos=0.5]
\tikzstyle{selected edge} = [draw,line width=2pt,-,red!50]
\tikzstyle{ignored edge} = [draw,line width=5pt,-,black!20]

\tikzset{
  treenode/.style = {align=center, inner sep=0pt, text centered,
    font=\sffamily},
  vertex/.style = {treenode, circle, black, font=\sffamily\bfseries\tiny, draw=black, text width=1.8em},% arbre rouge noir, noeud noir
  rvertex/.style = {treenode, circle, black, font=\sffamily\bfseries\tiny, draw=red, text width=1.8em},% arbre rouge noir, noeud noir
}

\begin{document}
\maketitle


\begin{frame}{Today we're going to cover}
    \vspace{40pt}
    \bi
        \item Dynamic Programming
    \ei
\end{frame}

\begin{frame}{What is dynamic programming?}
    \bi
        \item A problem solving paradigm
        \item Similar in some respects to both divide and conquer and backtracking
        \vspace{5pt}
        \item Divide and conquer recap:
            \bi
                \item Split the problem into \textit{independent} subproblems
                \item Solve each subproblem recursively
                \item Combine the solutions to subproblems into a solution for the given problem
            \ei
        \vspace{5pt}
        \item Dynamic programming:
            \bi
                \item Split the problem into \textit{overlapping} subproblems
                \item Solve each subproblem recursively
                \item Combine the solutions to subproblems into a solution for the given problem
                \item \textit{Don't compute the answer to the same subproblem more than once}
            \ei
    \ei
\end{frame}

\begin{frame}[fragile]{Dynamic programming formulation}
    \vspace{30pt}
    \be
        \item Formulate the problem in terms of smaller versions of the problem (recursively)
        \item Turn this formulation into a recursive function
        \item Memoize the function (remember results that have been computed)
    \ee
\end{frame}

\begin{frame}[fragile]{Dynamic programming formulation}
    \begin{minted}[fontsize=\footnotesize]{cpp}
map<problem, value> memory;

value dp(problem P) {
    if (is_base_case(P)) {
        return base_case_value(P);
    }

    if (memory.find(P) != memory.end()) {
        return memory[P];
    }

    value result = some value;
    for (problem Q in subproblems(P)) {
        result = combine(result, dp(Q));
    }

    memory[P] = result;
    return result;
}
    \end{minted}
\end{frame}

\begin{frame}{The Fibonacci sequence}
    \vspace{5pt}
    \textit{The first two numbers in the Fibonacci sequence are 1 and 1. All
            other numbers in the sequence are defined as the sum of the previous two
            numbers in the sequence.}

    \vspace{5pt}
    \bi
        \item Task: Find the $n$th number in the Fibonacci sequence
        \item Let's solve this with dynamic programming
    \ei

    \vspace{5pt}
    \be
        \item Formulate the problem in terms of smaller versions of the problem (recursively)
    \ee

    \begin{align*}
        \mathrm{fibonacci}(1) &= 1\\
        \mathrm{fibonacci}(2) &= 1\\
        \mathrm{fibonacci}(n) &= \mathrm{fibonacci}(n - 2) + \mathrm{fibonacci}(n - 1)
    \end{align*}
\end{frame}

\begin{frame}[fragile]{The Fibonacci sequence}
    \be
        \item[2.] Turn this formulation into a recursive function
    \ee

    \begin{minted}[fontsize=\footnotesize]{cpp}
int fibonacci(int n) {
    if (n <= 2) {
        return 1;
    }

    int res = fibonacci(n - 2) + fibonacci(n - 1);

    return res;
}
    \end{minted}
\end{frame}

\begin{frame}[fragile]{The Fibonacci sequence}
    \bi
        \item What is the time complexity of this? \onslide<2->{Exponential, almost $O(2^n)$}
    \ei

    \begin{figure}

        \begin{tikzpicture}

[-,thick,%
  every node/.style={shape=circle,draw,thick},%
  level distance=0.5cm,
  growth parent anchor={south}, nodes={anchor=north},
  scale=0.8,%
]
\scriptsize
\node {$fib(6)$}
  [sibling distance=5cm]
  child {node {$fib(4)$}
    [sibling distance=2cm]
    child {node {$fib(2)$}
      % [sibling distance=0.5cm]
      % % child {node {$0$}}
      % child {node {$fib(1)$}
      %   % child {node {$0$}}
      %   % child {node {$0$}}
      % }
    }
    child {node {$fib(3)$}
      [sibling distance=1cm]
      child {node {$fib(1)$}
        [sibling distance=0.5cm]
        % child {node {$0$}}
        % child {node {$0$}}
      }
      child {node {$fib(2)$}
        % [sibling distance=0.5cm]
        % % child {node {$0$}}
        % child {node {$fib(1)$}
        %   % child {node {$0$}}
        %   % child {node {$0$}}
        % }
      }
    }
  }
  child {node {$fib(5)$}
    [sibling distance=3cm]
    child {node {$fib(3)$}
      [sibling distance=1cm]
      child {node {$fib(1)$}
        [sibling distance=0.5cm]
        % child {node {$0$}}
        % child {node {$0$}}
      }
      child {node {$fib(2)$}
        % [sibling distance=0.5cm]
        % % child {node {$0$}}
        % child {node {$fib(1)$}
        %   % child {node {$0$}}
        %   % child {node {$0$}}
        % }
      }
    }
    child {node {$fib(4)$}
      [sibling distance=2cm]
      child {node {$fib(2)$}
        % [sibling distance=0.5cm]
        % % child {node {$0$}}
        % child {node {$fib(1)$}
        %   % child {node {$0$}}
        %   % child {node {$0$}}
        % }
      }
      child {node {$fib(3)$}
        [sibling distance=1cm]
        child {node {$fib(1)$}
          [sibling distance=0.5cm]
          % child {node {$0$}}
          % child {node {$0$}}
        }
        child {node {$fib(2)$}
          % [sibling distance=0.5cm]
          % % child {node {$0$}}
          % child {node {$fib(1)$}
          %   % child {node {$0$}}
          %   % child {node {$0$}}
          % }
        }
      }
    }
  };
        \end{tikzpicture}

% \tikzset{
%   treenode/.style = {align=center, inner sep=0pt, text centered,
%     font=\sffamily},
%   vertex/.style = {treenode, circle, white, font=\sffamily\bfseries\tiny, draw=white,
%     text width=1.8em},% arbre rouge noir, noeud noir
% }
% 
% \begin{tikzpicture}
%     [->,>=stealth',level/.style={sibling distance = 5cm/#1,
%   level distance = 1.8cm},scale=0.8] 
%   \node [vertex] {fib(10)}
%     child{ node [vertex] {fib(8)}
%             child{ node [vertex] {fib(6)} 
%                 child{ node [vertex] {fib(4)} }
%                 child{ node [vertex] {fib(5)}}
%             }
%             child{ node [vertex] {fib(7)}
%                             child{ node [vertex] {fib(5)}}
%                             child{ node [vertex] {fib(6)}}
%             }
%     }
%     child{ node [vertex] {fib(9)}
%         child{ node [vertex] {fib(7)} 
%             child{
%                 node [vertex] {fib(5)}
%                     child { node [vertex] {fib(3)} }
%                     child { node [vertex] {fib(4)} }
%                 }
%             child{ node [vertex] {fib(6)}
%             }
%             }
%             child{ node [vertex] {fib(8)}
% 							child{ node [vertex] {49}}
% 							% child{ node [vertex] {}}
%             }
% 		}
% ; 
% \end{tikzpicture}
            \end{figure}

\end{frame}

\begin{frame}[fragile]{The Fibonacci sequence}
    \be
        \item[3.] Memoize the function (remember results that have been computed)
    \ee

    \vspace{5pt}

    \begin{minted}[fontsize=\footnotesize]{cpp}
map<int, int> mem;

int fibonacci(int n) {
    if (n <= 2) {
        return 1;
    }

    if (mem.find(n) != mem.end()) {
        return mem[n];
    }

    int res = fibonacci(n - 2) + fibonacci(n - 1);

    mem[n] = res;
    return res;
}
    \end{minted}

\end{frame}

\begin{frame}[fragile]{The Fibonacci sequence}
    \vspace{5pt}

    \begin{minted}[fontsize=\footnotesize]{cpp}
int mem[1000];
for (int i = 0; i < 1000; i++)
    mem[i] = -1;

int fibonacci(int n) {
    if (n <= 2) {
        return 1;
    }

    if (mem[n] != -1) {
        return mem[n];
    }

    int res = fibonacci(n - 2) + fibonacci(n - 1);

    mem[n] = res;
    return res;
}
    \end{minted}

\end{frame}

\begin{frame}{The Fibonacci sequence}
    \bi
        \item What is the time complexity now?
        \vspace{5pt}
        \item We have $n$ possible inputs to the function: $1$, $2$, \ldots, $n$.
        \item Each input will either:
            \bi
                \item be computed, and the result saved
                \item be returned from memory
            \ei
        \item Each input will be computed at most once
        \item Time complexity is $O(n \times f)$, where $f$ is the time complexity of computing an input if we assume that the recursive calls are returned directly from memory ($O(1)$)
        \item Since we're only doing constant amount of work to compute the answer to an input, $f = O(1)$
        \item Total time complexity is $O(n)$
    \ei
\end{frame}

\begin{frame}{Maximum sum}

    \vspace{10pt}

    \bi
\item Given an array $\mathrm{arr}[0]$, $\mathrm{arr}[1]$, \ldots, $\mathrm{arr}[n-1]$ of integers, find the interval with the highest sum
    \ei

    \begin{center}
        \begin{tabular}{|c|c|c|c|c|c|c|}
            \hline
            -15 & \color<2->{vhilight}{8} & \color<2->{vhilight}{-2} & \color<2->{vhilight}{1} & \color<2->{vhilight}{0} & \color<2->{vhilight}{6} & -3 \\
            \hline
        \end{tabular}
    \end{center}

    \bi
        \item<2-> The maximum sum of an interval in this array is $13$

        \item<3-> But how do we solve this in general?
            \bi
        \item Easy to loop through all $\approx n^2$ intervals, and calculate their sums, but that is $O(n^3)$
        \item We could use our static range sum trick to get this down to $O(n^2)$
        \item Can we do better with dynamic programming?
            \ei
    \ei

\end{frame}

\begin{frame}{Maximum sum}

    \vspace{20pt}

    \bi
        \item First step is to formulate this recursively
        \vspace{5pt}
        \item Let $\mathrm{max\_{}sum}(i)$ be the maximum sum interval in the range $0,\ldots,i$
        \vspace{5pt}
        \item Base case: $\mathrm{max\_{}sum}(0) = \mathrm{max}(0, arr[0])$
        \vspace{5pt}
        \item What about $\mathrm{max\_{}sum}(i)$?
        \item What does $\mathrm{max\_{}sum}(i-1)$ return?
        \item Is it possible to combine solutions to subproblems with smaller $i$ into a solution for $i$?
        \vspace{5pt}
        \item At least it's not obvious...
    \ei

\end{frame}

\begin{frame}{Maximum sum}

    \vspace{20pt}

    \bi
        \item Let's try changing perspective
        \vspace{5pt}
    \item Let $\mathrm{max\_{}sum}(i)$ be the maximum sum interval in the range $0,\ldots,i$, \textit{that ends at $i$}
        \vspace{5pt}
        \item Base case: $\mathrm{max\_{}sum}(0) = arr[0]$
        \vspace{5pt}
    \item $\mathrm{max\_{}sum}(i) = \mathrm{max}(arr[i], arr[i] + \mathrm{max\_{}sum}(i - 1))$
        \vspace{15pt}
        \item Then the answer is just $\mathrm{max}_{\ 0 \leq i < n}\ \{\ \mathrm{max\_{}sum}(i)\ \}$
    \ei

\end{frame}

\begin{frame}[fragile]{Maximum sum}
    \bi
        \item Next step is to turn this into a function
    \ei

    \begin{minted}{cpp}
int arr[1000];

int max_sum(int i) {
    if (i == 0) {
        return arr[i];
    }

    int res = max(arr[i], arr[i] + max_sum(i - 1));

    return res;
}
    \end{minted}
\end{frame}

\begin{frame}[fragile]{Maximum sum}
    \bi
        \item Final step is to memoize the function
    \ei

    \begin{minted}[fontsize=\scriptsize]{cpp}
int arr[1000];
int mem[1000];
bool comp[1000];
memset(comp, 0, sizeof(comp));

int max_sum(int i) {
    if (i == 0) {
        return arr[i];
    }
    if (comp[i]) {
        return mem[i];
    }

    int res = max(arr[i], arr[i] + max_sum(i - 1));

    mem[i] = res;
    comp[i] = true;
    return res;
}
    \end{minted}
\end{frame}

\begin{frame}[fragile]{Maximum sum}
    \bi
        \item Then the answer is just the maximum over all interval ends
    \ei

    \begin{minted}{cpp}
int maximum = 0;
for (int i = 0; i < n; i++) {
    maximum = max(maximum, best_sum(i));
}

printf("%d\n", maximum);
    \end{minted}
\end{frame}

\begin{frame}[fragile]{Maximum sum}
    \vspace{40pt}
    \bi
        \item If you want to find the maximum sum interval in multiple arrays, remember to clear the memory in between
    \ei
\end{frame}

\begin{frame}{Maximum sum}
    \vspace{20pt}
    \bi
        \item What about time complexity?
        \vspace{5pt}
        \item There are $n$ possible inputs to the function
        \item Each input is processed in $O(1)$ time, assuming recursive calls are $O(1)$
        \item Time complexity is $O(n)$
    \ei
\end{frame}

\begin{frame}{Coin change}
    \vspace{20pt}

    \bi
\item Given an array of coin denominations $d_0$, $d_1$, \ldots, $d_{n-1}$,
            and some amount $x$: What is minimum number of coins needed to
            represent the value $x$?

        \item Remember the greedy algorithm for Coin change?
        \item It didn't always give the optimal solution, and sometimes it didn't even give a solution at all...

        \vspace{10pt}
        \item What about dynamic programming?
    \ei
\end{frame}

\begin{frame}{Coin change}
    \bi
        \item First step: formulate the problem recursively
        \vspace{20pt}
\item Let $\mathrm{opt}(i,x)$ denote the minimum number of coins needed to represent the value $x$ if we're only allowed to use coin denominations $d_0$, \ldots, $d_i$
        \vspace{10pt}
        \item Base case: $\mathrm{opt}(i,x) = \infty$ if $x < 0$
        \item Base case: $\mathrm{opt}(i,0) = 0$
        \item Base case: $\mathrm{opt}(-1,x) = \infty$
        \vspace{10pt}
\item $\mathrm{opt}(i,x) = \mathrm{min} \left\{
	\begin{array}{l}
        1 + \mathrm{opt}(i, x - d_i) \\
        \mathrm{opt}(i-1, x)
	\end{array}
\right.$
    \ei
\end{frame}

\begin{frame}[fragile]{Coin change}
    \begin{minted}[fontsize=\footnotesize]{cpp}
int INF = 100000;
int d[10];

int opt(int i, int x) {
    if (x < 0) return INF;
    if (x == 0) return 0;
    if (i == -1) return INF;

    int res = INF;
    res = min(res, 1 + opt(i, x - d[i]));
    res = min(res, opt(i - 1, x));

    return res;
}
    \end{minted}
\end{frame}

\begin{frame}[fragile]{Coin change}
    \begin{minted}[fontsize=\footnotesize]{cpp}
int INF = 100000;
int d[10];
int mem[10][10000];
memset(mem, -1, sizeof(mem));

int opt(int i, int x) {
    if (x < 0) return INF;
    if (x == 0) return 0;
    if (i == -1) return INF;

    if (mem[i][x] != -1) return mem[i][x];

    int res = INF;
    res = min(res, 1 + opt(i, x - d[i]));
    res = min(res, opt(i - 1, x));

    mem[i][x] = res;
    return res;
}
    \end{minted}
\end{frame}

\begin{frame}{Coin change}
    \vspace{30pt}
    \bi
        \item Time complexity?
        \item Number of possible inputs are $n \times x$
        \item Each input will be processed in $O(1)$ time, assuming recursive calls are constant
        \item Total time complexity is $O(n\times x)$
    \ei
\end{frame}

\begin{frame}{Coin change}
    \bi
        \vspace{30pt}
        \item How do we know which coins the optimal solution used?
        \item We can store backpointers, or some extra information, to trace backwards through the states
        \item See example...
    \ei
\end{frame}

\begin{frame}{Longest increasing subsequence}
    \bi
\item Given an array $a[0]$, $a[1]$, \ldots, $a[n-1]$ of integers, what is the length of the longest increasing subsequence?
    \vspace{15pt}
\item First, what is a subsequence?
\item If we delete zero or more elements from $a$, then we have a subsequence of $a$
    \vspace{5pt}
\item Example: $a = [5,1,8,1,9,2]$
    \vspace{5pt}
\item $[5,8,9]$ is a subsequence
\item $[1,1]$ is a subsequence
\item $[5,1,8,1,9,2]$ is a subsequence
\item $[]$ is a subsequence
\item $[8,5]$ is \textbf{not} a subsequence
\item $[10]$ is \textbf{not} a subsequence
    \ei
\end{frame}

\begin{frame}{Longest increasing subsequence}
    \bi
\item Given an array $a[0]$, $a[1]$, \ldots, $a[n-1]$ of integers, what is the length of the longest increasing subsequence?
    \vspace{5pt}
\item An increasing subsequence of $a$ is a subsequence of $a$ such that the elements are in (strictly) increasing order
    \vspace{5pt}
\item $[5,8,9]$ and $[1,8,9]$ are the longest increasing subsequences of $a = [5,1,8,1,9,2]$

    \vspace{5pt}
\item How do we compute the length of the longest increasing subsequence?
\item There are $2^n$ subsequences, so we can go through all of them
\item That would result in an $O(n2^n)$ algorithm, which can only handle $n\leq 23$
    \vspace{5pt}
\item What about dynamic programming?

    \ei
\end{frame}

\begin{frame}{Longest increasing subsequence}
    \vspace{20pt}
    \bi
\item Let $\mathrm{lis}(i)$ denote the length of the longest increasing subsequence of the array $a[0]$, $\ldots$, $a[i]$
    \vspace{5pt}
\item Base case: $\mathrm{lis}(0) = 1$
\item What about $\mathrm{lis}(i)$?
    \vspace{10pt}
\item We have the same issue as in the maximum sum problem, so let's try changing perspective
    \ei
\end{frame}

\begin{frame}{Longest increasing subsequence}
    \vspace{40pt}
    \bi
\item Let $\mathrm{lis}(i)$ denote the length of the longest increasing subsequence of the array $a[0]$, $\ldots$, $a[i]$, \textit{that ends at $i$}
    \vspace{5pt}
\item Base case: we don't need one
\item $\mathrm{lis}(i) = \mathrm{max}(1, \mathrm{max}_{j<i \textrm{ s.t. } a[j] < a[i]} \{ 1 + \mathrm{lis}(j) \})$
    \ei
\end{frame}

\begin{frame}[fragile]{Longest increasing subsequence}
    \begin{minted}[fontsize=\footnotesize]{cpp}
int a[1000];
int mem[1000];
memset(mem, -1, sizeof(mem));

int lis(int i) {
    if (mem[i] != -1) {
        return mem[i];
    }

    int res = 1;
    for (int j = 0; j < i; j++) {
        if (a[j] < a[i]) {
            res = max(res, 1 + lis(j));
        }
    }

    mem[i] = res;
    return res;
}
    \end{minted}
\end{frame}

\begin{frame}[fragile]{Longest increasing subsequence}
    \vspace{30pt}

    \bi
        \item And then the longest increasing subsequence can be found by checking all endpoints:
    \ei

    \begin{minted}{cpp}
int mx = 0;
for (int i = 0; i < n; i++) {
    mx = max(mx, lis(i));
}

printf("%d\n", mx);
    \end{minted}
\end{frame}

\begin{frame}{Longest increasing subsequence}
    \vspace{30pt}
    \bi
        \item Time complexity?
            \vspace{10pt}
        \item There are $n$ possible inputs
        \item Each input is computed in $O(n)$ time, assuming recursive calls are $O(1)$
        \item Total time complexity is $O(n^2)$
            \vspace{10pt}
        \item This will be fast enough for $n \leq 10\ 000$, much better than the brute force method!
    \ei
\end{frame}


\begin{frame}{Longest common subsequence}
    \vspace{20pt}
    \bi
\item Given two strings (or arrays of integers) $a[0]$, \ldots, $a[n-1]$ and $b[0]$, \ldots, $b[m-1]$, find the length of the longest subsequence that they have in common.

    \vspace{10pt}
\item $a = $\texttt{"b\underline{an}an\underline{inn}"}
\item $b = $\texttt{"k\underline{anin}a\underline{n}"}
    \vspace{5pt}
\item The longest common subsequence of $a$ and $b$, \texttt{"aninn"}, has length 5
    \ei
\end{frame}

\begin{frame}{Longest common subsequence}
    \vspace{20pt}
    \bi
\item Let $\mathrm{lcs}(i, j)$ be the length of the longest common subsequence of the strings $a[0]$, \ldots, $a[i]$ and $b[0]$, \ldots, $b[j]$

    \vspace{10pt}
\item Base case: $\mathrm{lcs}(-1, j) = 0$
\item Base case: $\mathrm{lcs}(i, -1) = 0$
    \vspace{10pt}
\item $\mathrm{lcs}(i, j) = \mathrm{max} \left\{
	\begin{array}{ll}
        \mathrm{lcs}(i,j-1) & \\
        \mathrm{lcs}(i-1,j) & \\
        1 + \mathrm{lcs}(i-1,j-1) & \textrm{if } a[i] = b[j] \\
	\end{array}
\right.$
    \ei
\end{frame}

\begin{frame}[fragile]{Longest common subsequence}
    \begin{minted}[fontsize=\scriptsize]{cpp}
string a = "bananinn",
       b = "kaninan";
int mem[1000][1000];
memset(mem, -1, sizeof(mem));

int lcs(int i, int j) {
    if (i == -1 || j == -1) {
        return 0;
    }
    if (mem[i][j] != -1) {
        return mem[i][j];
    }

    int res = 0;
    res = max(res, lcs(i, j - 1));
    res = max(res, lcs(i - 1, j));

    if (a[i] == b[j]) {
        res = max(res, 1 + lcs(i - 1, j - 1));
    }

    mem[i][j] = res;
    return res;
}
    \end{minted}
\end{frame}

\begin{frame}{Longest common subsequence}
    \vspace{40pt}
    \bi
        \item Time complexity?
            \vspace{10pt}
        \item There are $n\times m$ possible inputs
        \item Each input is processed in $O(1)$, assuming recursive calls are $O(1)$
        \item Total time complexity is $O(n\times m)$
    \ei
\end{frame}

\begin{frame}{DP over bitmasks}
    \vspace{40pt}
    \bi
        \item Remember the bitmask representation of subsets?
        \item Each subset of $n$ elements are mapped to an integer in the range $0$, \ldots, $2^{n} - 1$
        \item This makes it easy to do dynamic programming over subsets
    \ei
\end{frame}

\begin{frame}{Traveling salesman problem}
    \vspace{10pt}

    \bi
        \item We have a graph of $n$ vertices, and a cost $c_{i,j}$ between each pair of vertices $i, j$. We want to find a cycle through all vertices in the graph so that the sum of the edge costs in the cycle is minimal.

        \vspace{5pt}
        \item This problem is NP-Hard, so there is no known deterministic polynomial time algorithm that solves it

        \vspace{10pt}
        \item Simple to do in $O(n!)$ by going through all permutations of the vertices, but that's too slow if $n > 11$

        \vspace{10pt}
        \item Can we go higher if we use dynamic programming?
    \ei
\end{frame}

\begin{frame}{Traveling salesman problem}
    \vspace{20pt}
    \bi
\item Without loss of generality, assume we start and end the cycle at vertex $0$
    \vspace{10pt}

\item Let $\mathrm{tsp}(i, S)$ represent the cheapest way to go through all vertices in the graph and back to vertex $0$, if we're currently at vertex $i$ and we've already visited the vertices in the set $S$

    \vspace{20pt}
\item Base case: $\mathrm{tsp}(i, \textrm{all vertices}) = c_{i,0}$
\item Otherwise $\mathrm{tsp}(i, S) = \mathrm{min}_{\ j \not\in S\ } \{\ c_{i,j} + \mathrm{tsp}(j, S \cup \{j\})\ \}$
    \ei
\end{frame}

\begin{frame}[fragile]{Traveling salesman problem}
    \begin{minted}[fontsize=\scriptsize]{cpp}
const int N = 20;
const int INF = 100000000;
int c[N][N];
int mem[N][1<<N];
memset(mem, -1, sizeof(mem));

int tsp(int i, int S) {
    if (S == ((1 << N) - 1)) {
        return c[i][0];
    }
    if (mem[i][S] != -1) {
        return mem[i][S];
    }

    int res = INF;
    for (int j = 0; j < N; j++) {
        if (S & (1 << j))
            continue;

        res = min(res, c[i][j] + tsp(j, S | (1 << j)));
    }

    mem[i][S] = res;
    return res;
}
    \end{minted}
\end{frame}

\begin{frame}[fragile]{Traveling salesman problem}
    \vspace{30pt}
    \bi
\item Then the optimal solution can be found as follows:
    \ei

    \vspace{20pt}
    \begin{minted}{cpp}
printf("%d\n", tsp(0, 1<<0));
    \end{minted}
\end{frame}

\begin{frame}{Traveling salesman problem}
    \vspace{30pt}
    \bi
        \item Time complexity?
        \vspace{10pt}
        \item There are $n \times 2^n$ possible inputs
        \item Each input is computed in $O(n)$ assuming recursive calls are $O(1)$
        \item Total time complexity is $O(n^2 2^n)$
            \vspace{10pt}
        \item Now $n$ can go up to about $20$
    \ei
\end{frame}

\begin{frame}[fragile]{Traveling salesman problem}
    % http://xkcd.com/399/
    \vspace{40pt}
    \begin{center}
    \ig[scale=0.4]{travelling_salesman_problem.png}
    \end{center}
\end{frame}

\end{document}

